import org.junit.Test;

import java.util.*;

public class Solution39 {
    /**
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * <p>
     * candidates 中的数字可以无限制重复被选取。
     * <p>
     * 说明：
     * <p>
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。 
     * 示例 1:
     * <p>
     * 输入: candidates = [2,3,6,7], target = 7,
     * 所求解集为:
     * [
     * [7],
     * [2,2,3]
     * ]
     */
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<Integer> track = new ArrayList<>();
        fun(candidates, target, track, 0);
        return ans;

    }

    public void fun(int[] candidates, int target, List<Integer> track, int startIndex) {

        if (target == 0) {
            ans.add(new ArrayList<>(track));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
                continue;
            } else {
                track.add(candidates[i]);
                fun(candidates, target - candidates[i], track, i);
                track.remove(track.size() - 1);
            }
        }
    }

    @Test
    public void test(){
        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
    }
}
